package leetcode

//https://leetcode.com/problems/generate-parentheses/
/**
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
 */
//Classic 完美解释
//https://www.youtube.com/watch?v=sz1qaKt0KGQ
/**
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
 */

fun main(args: Array<String>) {
    println(generateParenthesis(3))
}

fun generateParenthesis(n: Int): List<String> {

    val result = arrayListOf<String>()
    generateParentthesis(n, n, "", result, n)
    return result
}

fun generateParentthesis(l: Int, r: Int, str: String, result: ArrayList<String>, n: Int) {

    if (l == 0 && r == 0) result.add(str)

    if (l > 0) generateParentthesis(l - 1, r, str.plus("("), result, n)

    if (l < r) generateParentthesis(l, r - 1, str.plus(")"), result, n)
}